package mine.code.practice;

import org.junit.Test;

import java.util.Arrays;
import java.util.Stack;

/**
 * 单调栈联系
 * 针对一个随机数组,判断数组内每一位数字需要向右多少可以碰到第一个比它大的数,没有则返回负一,返回改组成数组
 * 例:
 * input: [5,4,7,1]
 * output: [2,1,-1,-1]
 * input: [5,3,1,2,4]
 * return: [-1,3,1,1,-1]
 *
 * @author caijinnan
 */
public class 单调栈 {


    @Test
    public void run() {
        int[] a = {5, 3, 1, 2, 4};
        System.out.println(Arrays.toString(practice(a)));
    }

    public int[] practice(int[] inputArr) {
        Stack<Integer> stack = new Stack<>();
        int length = inputArr.length;
        int[] out = new int[length];
        for (int i = 0; i < length; i++) {
            out[i] = -1;
            while(!stack.empty() && inputArr[stack.peek()] < inputArr[i]) {
                out[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }
        return out;
    }

}
